package com.zhn;

/**
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 *
 */

import java.util.Arrays;

public class BuildTreeB {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int i_len = inorder.length;
        int p_len = postorder.length;
        if(i_len == 0||p_len == 0){
            return null;
        }
        //通过后序序列，查找子树的根节点
        int root_val = postorder[p_len-1];
        //构造根节点
        TreeNode root = new TreeNode(root_val);
        //遍历中序序列，确定根节点在中序序列中的位置，从而确定左右子树
        int k = 0;
        for(int i = 0; i < i_len; i++){
            if(root_val == inorder[i]){
                k = i;
                break;
            }
        }
        //分割左右子树，分别创建左右子树的中序和后序序列
        int[] left_in = Arrays.copyOfRange(inorder,0,k);
        int[] left_post = Arrays.copyOfRange(postorder,0,k);
        root.left = buildTree(left_in,left_post);

        //中序的根节点已经被拿走了，所以要加一跳过
        int[] right_in = Arrays.copyOfRange(inorder,k+1,i_len);
        //后序根节点已经被拿走，所以要减一
        int[] right_post = Arrays.copyOfRange(postorder, k, p_len - 1);
        root.right = buildTree(right_in,right_post);
        return root;
    }
}
